package com.util;

import fundation.tree.BTreePrinter;
import fundation.tree.Node;
import org.junit.Test;

import java.lang.reflect.Field;
import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
import java.util.*;

/**
 * 根据优先级高的先出队列，可以用来实现小顶堆(节点的优先级大于左右子节点的优先级)
 */
public class PriorityQueueDemo {


    /**
     * 构造函数，可以用来初始化一个Collection对象,并在初始化时堆化该集合
     * initFromCollection(),initElementsFromCollection()从集合中初始化队列
     * heapify()堆化该队列，
     * siftDown(i,e)
     *
     * @throws NoSuchFieldException
     * @throws IllegalAccessException
     */
    @Test
    public void constructor() throws NoSuchFieldException, IllegalAccessException {
        List<String> conllection = new ArrayList<>();
        conllection.add("c");
        conllection.add("a");
        conllection.add("b");
        PriorityQueue<String> priorityQueue = new PriorityQueue(conllection);
        Field queue = priorityQueue.getClass().getDeclaredField("queue");
        queue.setAccessible(true);
        //实际存储的顺序（二叉树数组的顺序）
        Object[] o = (Object[]) queue.get(priorityQueue);
        for (Object t : o) {
            System.out.println(t);
        }

        System.out.println("--------");
        //从队列中取出数据的顺序
        String t = null;
        while ((t= priorityQueue.poll())!=null){
            System.out.println(t);
        }
    }

    /**
     * 比较器，将长度小的先出队列
     */
    @Test
    public void constructor01() {
        Queue<String> queue = new PriorityQueue<>(Comparator.comparingInt(String::length));
        queue.offer("aaa");//等价于add
        queue.offer("b");
        queue.offer("cc");
        //peek只是取出头元素不会删除
        System.out.println(queue.peek());
        System.out.println(queue.peek());
        System.out.println(queue.peek());

        //取出头元素并从队列中删除
        System.out.println(queue.poll());
        System.out.println(queue.poll());
        System.out.println(queue.poll());
    }

    /**
     * 当每次新增元素时需要判断容量是否满足。
     * 扩容策略，若容量小于64,则扩容为当前容量的两倍+2否则扩容1.5倍。
     * 不清楚设置的原因?以及MAX_ARRAY_SIZE最大容量的设置
     */
    @Test
    public void grow() throws NoSuchMethodException, InvocationTargetException, IllegalAccessException, NoSuchFieldException {
        Queue<String> queue = new PriorityQueue<>();
        Method grow = queue.getClass().getDeclaredMethod("grow", int.class);
        grow.setAccessible(true);
        grow.invoke(queue, 20);

        //实际容量
        Field queueData = queue.getClass().getDeclaredField("queue");
        queueData.setAccessible(true);
        System.out.println(((Object[])queueData.get(queue)).length);
    }


    /**
     * 每次remove或者poll时，从指定位置移除元素，并将queue最后一个元素尝试放到当前位置，并进行下沉
     * siftDown(i,e)尝试将e放置到queue的第i个位置，若不满足堆，则将e下沉到对应的节点
     */
    @Test
    public void siftDown(){

    }

    /*
     * 移除queue数组中的第i个元素，因为是从数组中间移除的元素，所以将队尾的元素放置到i位置时，需要进行下沉，若未产生，则需要进行上浮。下面两颗树,移除9时，需要将6移动到9所在的位置,因为未产生下沉,所以进行上浮操作,然后6小于7所以6上浮到7的位置
1,7,3,8,9,6,    1,6,3,8,7,
   1                1
  / \              / \
 /   \            /   \
 7   3  ->        6   3
/ \ /            / \
8 9 6            8 7
     */
    @Test
    public void removeAt(){

    }

    /**
     * offer或者add时在队尾添加元素并将该元素进行上浮
     */
    @Test
    public void siftUp(){

    }

    /**
     * 找到该元素对应在queue的坐标位置
     */
    @Test
    public void indexOf(){

    }

    @Test
    public void toArray() {
        Queue<String> queue = new PriorityQueue();
        queue.offer("a");
        queue.offer("b");
        queue.offer("c");

        //使用toArray时，当数组长度小于queue中的对象数组长度，此时返回一个新的对象(string)，而不是使用原先旧的对象（array）
        String[] array = new String[2];
        String[] strings = queue.toArray(array);
        System.out.println(array);//所有元素为空
        System.out.println(strings);//返回queue中的所有元素
    }

    /**
     * 迭代器是并不是按照优先级遍历元素的，而是根据queue数组的存储顺序进行遍历元素。在此迭代器中remove元素时，其实是将queue数组中的第i个元素进行删除，删除元素时会重新结构化小顶堆，导致queue的数组数据产生变化，当产生后面的数据移动到i前面时,需要将移动到i前面的数据缓存到 forgetMeNot 对象中，以防遍历时数据未被遍历到。
     * 如下面的样例中，当移除9时，此时完全二叉树结构发生变化，6被移动到9所在位置的前面。所以将6存储到 forgetMeNot 对象中
     */
    @Test
    public void iterator() {
        Queue priorityQueue = new PriorityQueue();
        priorityQueue.offer(1);
        priorityQueue.offer(7);
        priorityQueue.offer(3);
        priorityQueue.offer(8);
        priorityQueue.offer(9);
        priorityQueue.offer(6);

//        printQueueData(priorityQueue);

        Iterator iterator = priorityQueue.iterator();
        while(iterator.hasNext()){
            Integer next =(Integer) iterator.next();
            System.out.println(next);
            if(next.equals(9)) {
                printQueueData(priorityQueue);
                iterator.remove();
                printQueueData(priorityQueue);
            }
        }

    }

    /**
     * 返回队首的元素，并将队尾的元素放到头位置使用siftDown进行下沉
     */
    @Test
    public void poll(){

    }

    /**
     * 将队列序列化，readObject反序列化
     */
    @Test
    public void writeObject(){

    }

    private void printQueueData(Queue q){
        Field queue = null;
        try {
            queue = q.getClass().getDeclaredField("queue");
            queue.setAccessible(true);
            //实际存储的顺序（二叉树数组的顺序）
            Object[] o = (Object[]) queue.get(q);
            Integer[] oArr = Arrays.copyOf(o, q.size(),Integer[].class);

            StringBuilder sb = new StringBuilder();
            for (Integer integer : oArr) {
                sb.append(integer).append(",");
            }
            System.out.println(sb);

            Node root = new Node<>();
            root = Node.createInstanceFromList(oArr);
            BTreePrinter.printNode(root);
        } catch (NoSuchFieldException e) {
            e.printStackTrace();
        } catch (IllegalAccessException e) {
            e.printStackTrace();
        }
    }


}
